Search for: All records

Abstract The SAT problem is a prototypical NP-complete problem of fundamental importance in computational complexity theory with many applications in science and engineering; as such, it has long served as an essential benchmark for classical and quantum algorithms. This study shows numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (G-QAOA) over random sampling for finding all solutions to 3-SAT (All-SAT) and Max-SAT problems. G-QAOA is less resource-intensive and more adaptable for these problems than Grover’s algorithm, and it surpasses conventional QAOA in its ability to sample all solutions. We show these benefits by classical simulations of many-round G-QAOA on thousands of random 3-SAT instances. We also observe G-QAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. Interestingly, a single-angle-pair constraint that uses the same pair of angles at each G-QAOA round greatly reduces the classical computational overhead of optimizing the G-QAOA angles while preserving its quadratic speedup. We also find parameter clustering of the angles. The single-angle-pair protocol and parameter clustering significantly reduce obstacles to classical optimization of the G-QAOA angles. 

Abstract Ultracold polar molecules combine a rich structure of long-lived internal states with access to controllable long-range anisotropic dipole–dipole interactions. In particular, the rotational states of polar molecules confined in optical tweezers or optical lattices may be used to encode interacting qubits for quantum computation or pseudo-spins for simulating quantum magnetism. As with all quantum platforms, the engineering of robust coherent superpositions of states is vital. However, for optically trapped molecules, the coherence time between rotational states is typically limited by inhomogeneous differential light shifts. Here we demonstrate a rotationally magic optical trap for⁸⁷Rb¹³³Cs molecules that supports a Ramsey coherence time of 0.78(4) s in the absence of dipole–dipole interactions. This is estimated to extend to >1.4 s at the 95% confidence level using a single spin-echo pulse. In our trap, dipolar interactions become the dominant mechanism by which Ramsey contrast is lost for superpositions that generate oscillating dipoles. By changing the states forming the superposition, we tune the effective dipole moment and show that the coherence time is inversely proportional to the strength of the dipolar interaction. Our work unlocks the full potential of the rotational degree of freedom in molecules for quantum computation and quantum simulation. 

Abstract Combinatorial optimization problems on graphs have broad applications in science and engineering. The quantum approximate optimization algorithm (QAOA) is a method to solve these problems on a quantum computer by applying multiple rounds of variational circuits. However, there exist several challenges limiting the application of QAOA to real-world problems. In this paper, we demonstrate on a trapped-ion quantum computer that QAOA results improve with the number of rounds for multiple problems on several arbitrary graphs. We also demonstrate an advanced mixing Hamiltonian that allows sampling of all optimal solutions with predetermined weights. Our results are a step toward applying quantum algorithms to real-world problems.